挑战赛#8题解
T1:
题目要求求出数轴上被同时涂成红色和蓝色的部分的长度。
其中[L1,R1]为蓝色 [L2,R2]为红色
纯模拟或者直接算即可
模拟代码 不用思考非常适合我:
时间复杂度O(n)O(n)O(n)
但是可以简化为什么要写模拟
计算代码:
时间复杂度O(1)O(1)O(1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T2
题目要求判断给定的比赛结果是否存在矛盾。
因为数据很小 n≥1000n\ge1000n≥1000 所以直接枚举每一个结果即可
有句话说得好:暴力出奇迹
代码如下:
时间复杂度O(n2)O(n^2)O(n2)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T3
题目要求统计字符串出现的次数。
注意第二次出现的时候要输出的是1
用STL模版中的 map 会很简单
不会STL模版可以参考Macw07大佬的帖子
代码如下:
时间复杂度O(nlog2n)O(n\log_2n)O(nlog2 n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
后三题和前三题完全不是一个难度的,天才出题组
T4
先说算法:动态规划+前缀和
我们设dp[i]表示i次抛硬币时能获取的最大价值
用sumA与sumB存储钱和额外奖金的前缀和
注意奖金的前缀和,sumB[i]指计数器到i时获得的额外奖金总数
我们假设在j次抛硬币选择反面,于是我们就能得到dp[i]的转移方程如下
dp[i]=max(dp[i],dp[j]+sumA[i]-sumA[j+1]+sumB[i-j-1]);
代码如下:
时间复杂度大约Θ(n22)\Theta(\frac{n^2}{2})Θ(2n2 )
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T5
这道题可以通过前缀位运算和动态规划来做
定义一个dp[i][0/1(j)][k]表示第i位的数字一开始的值(j)经过k轮后的值。
则根据定义我们可以得到转移方程为dp[i][j][k]=dp[i][j][k-1]|x(&x,^x)
取a的第i位可以通过a>>i&1实现
例如二进制10110要取第三位的1
右移三(i)位得到00101发现第三位到了第一位上
我们在&1 即00101&00001
因为&运算是都为1时取1,其余取0
发现如果第一位是1是刚好取1,是0时刚好取0
其余位因为&的1都是0,所以得数也是0
答案就是a的第i位
初始化为 dp[i][j][0]=j 因为不经过变换时当前位的数字不变
最后将dp[][][k]数组经过位运算还原
AC代码:
时间复杂度Θ(60n)\Theta(60n)Θ(60n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
T6
一道和逆序对很像的题
首先先讲述逆序对怎么做,题目 逆序对
对于一个数组 3 4 2 4 5 1 我们对它进行归并排序
当有序数组合并时,如果后半段大,则逆序对的数量加上前半段当前的长度
举个例子
比如:[2 3 4][1 4 5]时 后半段第一个 1 比前半段的第一个 2 大
因为归并排序的性质,数组的前半段和后半段都是有序的
则如果后半段第一个数比前半段第一个数小,则前半段所有的数都比他大
不难发现此时[2,1],[3,1][4,1]则前半段的所有数与后半段第一个都是逆序对
则此时让ans+=前半段的长度就是逆序对的答案
逆序对代码如下:
时间复杂度O(nlog2n)O(n\log_2n)O(nlog2 n)
回到这题来看,不难看出也是要求求出逆序对的数量,但是不同的是对于相同颜色的两个球不需要增加ans,那么我们考虑用一个cnt[]数组记录颜色的数量,在增加ans的时候减去cnt[后半段的颜色]。
AC代码如下:
时间复杂度O(nlog2n)O(n\log_2n)O(nlog2 n)